1. Field of the Invention
The present invention relates to collision detection. In particular, the present invention relates to collision detection that can be performed in a Graphics Processing Unit (GPU) and, more particularly, to a method of detecting collisions in parallel for a plurality of collision detection objects.
2. Description of the Related Art
Collision detection is the problem of determining overlapping or interference occurring between collision detection objects that are moving in a space. Collision detection becomes an issue in various fields such as computer graphics, computer animation, virtual reality, geometric modeling, haptics, and robotic engineering.
Collision detection technology is mainly classified into broad-phase algorithms and narrow-phase algorithms. Broad-phase algorithms are intended to determine possible intersecting pairs from n collision detection objects, and narrow-phase algorithms are intended to determine one pair from collision detection objects determined by the broad-phase algorithms. The present invention relates to such a broad-phase algorithm, which is also referred to as ‘n-body collision culling’.
There is required the flow simulation of collision detection objects conducted on several millions of particles in particle-based simulation areas, such as Distinct-element Method (DEM), Smoothed Particle Hydrodynamics (SPH), and Moving-Particle Semi-implicit (MPS). Further, in Massively Multi-Player Online Role-Playing Game (MMORPG), as a minimum of several thousands of users log in to the same server and perform activity therein, they interact with several tens of thousands of characters and surrounding collision detection objects. In many application fields including these examples, there is required collision detection technology for obtaining higher processing speed while conducting detection on a very large number of collision detection object sets.
The best-known broad-phase collision detection algorithm includes a Sweep and Prune (SaP) technique and a spatial subdivision technique. SaP is an access method configured to reduce a dimensional space by performing an overlap test that sweeps a hyperplane along a dimensional spatial axis when collision detection objects are projected into a low-dimensional space (generally, one-dimensional space). Spatial subdivision is a spatial hashing technique for performing a local intersection test in any type of grid for collision detection objects registered in the grid.
SaP is effective when moving collision detection objects have high spatial coherence at the time of performing a sweep operation, but is problematic in that efficiency is worse in the opposite case. Spatial subdivision is effective in the case of collision detection objects of the same size, but is problematic in that efficiency is worse in the case of a structure having a complicated system.
Therefore, it can be concluded that what is required is a fast collision detection algorithm that is applicable without being limited by the size of or the movement tendency of collision detection objects.